#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() :val(0),next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {

public:
    Solution() {};

    ~Solution() {};
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr &&list2 == nullptr) {
            return nullptr;
        } else if(list1 == nullptr) {
            return list2;
        } else if(list2 == nullptr) {
            return list1;
        }
        ListNode * begin, *p;
        if(list1->val < list2->val) {
            begin = p = list1;
            list1 = list1 -> next;
        } else {
            begin = p = list2;
            list2 = list2 -> next;
        }
        while(list1 != nullptr && list2 != nullptr) {
            if(list1->val < list2->val) {
                p->next = list1;
                list1 = list1 -> next;
            } else {
                p-> next = list2;
                list2 = list2-> next;
            }
            p = p-> next;
        }
        if(list1 != nullptr) {
            p -> next = list1;
        }
        if(list2 != nullptr) {
            p ->next = list2;
        }
        return begin;
    }

};


int main()
{

    return 0;
}